package ArraySeries;

public class ProductExceptSelfSolution_hot100_238 {
    public int[] productExceptSelf(int[] nums) {
        //利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案
        int[] result = new int[nums.length];

        // 给定索引 i
        // L[i] 代表的是 i 左侧所有数字的乘积，
        // R[i] 代表的是 i 右侧所有数字的乘积
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = nums[i - 1] * left[i - 1];
        }
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = nums[i + 1] * right[i + 1];
        }

        for (int i = 0; i < nums.length; i++) {
            result[i] = left[i] * right[i];
        }

        return result;
    }
}
